package com.aaron.leetcode.lc05;

/**
 * @author liurong
 * @date 2022/1/21 18:43
 * @version:
 */

//leetcode submit region begin(Prohibit modification and deletion)
class Solution05_2 {

    /*
        迭代解法:从小到大，自底向上
        对称的结构的for写法
        for(i=0/len)
            for(j=i)
     */

    public String longestPalindrome(String s) {
        // 处理异常情况
        if(s==null||s.length()<=1) return s;
        // dp[i][j] 表示从i到j的字符串中的最长子串
        // dp[i][i] 表示单个字符肯定是回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];
        String result= null;
        int length = -1;
        for(int i = s.length()-1;i>=0;i--){
            for(int j = i;j<s.length();j++ ){
                if(i==j) dp[i][j] = true;
                else if(j-i==1&&s.charAt(i)==s.charAt(j)) dp[i][j] = true;
                else if(s.charAt(i)==s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = false;
                if(dp[i][j]&&j-i>length){
                    length = j-i;
                    result = s.substring(i,j+1);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution05_2 solution05_2 = new Solution05_2();
        String s = "cbbd";
        System.out.println(solution05_2.longestPalindrome(s));
    }


}

